package com.zk.algorithm;

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindowMaximum {

    public static void main(String...args) {
        int[] r = new SlidingWindowMaximum().maxSlidingWindow(new int[]{ 1,3,-1,-3,5,3,6,7 }, 2);
        Utils.println(r);
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        // 保存的是元素的索引
        //
        // 为什么要保存索引，因为我们要判断当前是否 outOfRange
        // i - deque.peek() >= k
        Deque<Integer> deque = new ArrayDeque<Integer>();

        int[] result = new int[nums.length - k + 1];
        int rIndex = 0;

        for (int i=0; i<nums.length; i++) {

            // 移除头
            while (outOfRange(deque, i, k)) {
                deque.poll();
            }

            int curr = nums[i];
            // 移除尾
            while (!deque.isEmpty() &&
                    /** 新来的元素与前面的元素一一PK，角逐出 maximum **/
                    curr >= nums[deque.peekLast()]) {
                deque.pollLast();
            }

            deque.offer(i);

            // 可以放了
            // 从第 2 个元素起，我们就可以输出结果了
            if (i + 1 >= k) {
                result[rIndex++] = nums[deque.peek()];
            }
        }

        return result;
    }

    // Out of range
    private boolean outOfRange(Deque<Integer> deque, int i, int k) {
        return !deque.isEmpty() && (i - deque.peek() >= k);
    }

}